package Leetcode.数组字符串;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/4/18 11:15
 * @Description:
 * 从双倍数组中还原原数组
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
 *
 * 给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
 *
 *
 *
 * 示例 1：
 *
 * 输入：changed = [1,3,4,2,6,8]
 * 输出：[1,3,4]
 * 解释：一个可能的 original 数组为 [1,3,4] :
 * - 将 1 乘以 2 ，得到 1 * 2 = 2 。
 * - 将 3 乘以 2 ，得到 3 * 2 = 6 。
 * - 将 4 乘以 2 ，得到 4 * 2 = 8 。
 * 其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
 * 示例 2：
 *
 * 输入：changed = [6,3,0,1]
 * 输出：[]
 * 解释：changed 不是一个双倍数组。
 * 示例 3：
 *
 * 输入：changed = [1]
 * 输出：[]
 * 解释：changed 不是一个双倍数组。
 *
 *
 * 提示：
 *
 * 1 <= changed.length <= 105
 * 0 <= changed[i] <= 105
 */

public class findOriginalArray {
    public static void main(String[] args) {
        int[] arr = {1,3,4,2,6,8};
        System.out.println(Arrays.toString(findOriginalArray(arr)));

    }

    /**
     * 感觉可以先排序
     * 1    2   3   4   6   8
     * 2    3   4   6
     * 但是不能用二分查找或者说加一点约束条件？？
     *  用一个中间变量存一下感觉可以试试
     *
     * nlogn
     * @param changed
     * @return
     */
    public static int[] findOriginalArray(int[] changed) {
        int len = changed.length;
        if (len % 2 != 0) {
            return new int[0];
        }
        Arrays.sort(changed);
        int[] temp = new int[len];
        for (int i = 0; i < len; i++) {
            //这里二分查找找到了的话，需要把二倍数移除出去，就不用二倍数的二倍数了
            //这里数组的话我就把他置为-1  因为题目规定每个数都是>=0的
            if (changed[i] == -1) {
                temp[i] = -1;
                continue;
            }
            int double_num = changed[i] * 2;
            int double_num_index = find(changed, i + 1, double_num);
            //找到了  temp存一下，然后二倍数的那个数就不需要找了，置为-1
            //这里可能会越界，我在二分里边做了一个特殊判断
            if (changed[double_num_index] == double_num) {
                temp[i] = changed[i];
                changed[double_num_index] = -1;
            }else {
                temp[i] = -1;
            }
        }
        //存找不到对应两倍数的数有多少个
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (temp[i] == -1) {
                count++;
            }
        }
        //大于一半的话肯定不是一个双倍数组
        if (count > len / 2) {
            return new int[0];
        }
        int[] ans = new int[len / 2];
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (temp[i] != -1) {
                ans[index] = temp[i];
                index++;
            }
        }
        return ans;
    }

    public static int find(int[] nums,int left, int target) {
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left == nums.length ? nums.length - 1 : left;
    }

    /**
     * 确实用map  get更快！没想到，害。只想着怎么找去了
     * @param changed
     * @return
     */
    public int[] findOriginalArray2(int[] changed) {
        Arrays.sort(changed);
        Map<Integer, Integer> count = new HashMap<>();
        for (int a : changed) {
            count.put(a, count.getOrDefault(a, 0) + 1);
        }
        int[] res = new int[changed.length / 2];
        int i = 0;
        for (int a : changed) {
            if (count.get(a) == 0) {
                continue;
            }
            count.put(a, count.get(a) - 1);
            if (count.getOrDefault(a * 2, 0) == 0) {
                return new int[0];
            }
            count.put(a * 2, count.get(a * 2) - 1);
            res[i++] = a;
        }
        return res;
    }
}
